1. Field of the Invention
The present invention relates generally to a parity check matrix for a linear block encoder and decoder in a data transmission system. More particularly, the present invention relates to a parity check matrix and method of forming thereof for a low-density parity check code (LDPC) encoder for a write channel and decoder for a read channel in a disk drive system.
2. Background Information
FIGS. 1 and 2 illustrate data transmission systems each employing a linear block code encoder on the transmission side and a soft linear block code decoder on the receiver side. The linear block code utilized in various systems includes a low-density parity check (LDPC) code.
With either system, the parity check matrix is an important element in a low-density parity check (LDPC) code. The parity check matrix effects system performance in terms of computation efficiency, accuracy and reliability. A linear code is a set of codewords, x, satisfying the matrix equation (1)H·x=0  (1)where H is an M×N matrix, and x is a 1×N vector.
The parity check matrix for an LDPC encoder/decoder is sparse, that is, a small portion of the elements being one, all other elements being zero. An example of a parity check matrix is shown in equation 2 that corresponds to the factor graph shown in FIG. 3.
                    H        =                  [                                                    1011                                                                    0111                                              ]                                    (        2        )            which defines the following parity check equations for the codeword xx1+x3+x4  =0x2+x3+x4  =0
FIG. 3 is a factor graph of the parity matrix of equation 2. The factor graph contains two types of nodes the bit node (e.g., b1, b2, b3, and b4) and the check nodes (e.g., e1, e2). Each bit node corresponds to a bit in the codeword, and each check node represents a parity check equation (i.e., a row in the parity check matrix H). Hence, the factor graph for an LDPC code with an M×N parity check matrix H contains M check nodes and N bit nodes. An edge between a check node and a bit node exists if and only if the bit participates in the parity check equation represented by the check node. The factor graph shown in FIG. 3 is “bipartite” in which the nodes can be separated to two groups, namely check nodes and bit nodes. Connections are allowed only between nodes in different groups.
A cycle in a factor graph refers to a finite set of connected edges that start and end at the same node. The bold lines in FIG. 3 represent a cycle length of four. As can be appreciated by one of ordinary skill in the art, four is the shortest cycle length a parity check matrix can have. The inventors have observed that the existence of period-4 cycles causes degradation in performance of sum-product decoding algorithms. The sum-product algorithm is discussed by Zining Wu in Coding and Iterative Detection For Magnetic Recording Channels, 2000, Kluwer Academic Publishers, pages 55–60, the contents of which are incorporated by reference herein.
One example of a conventional parity check is the simple parity check (SPC) matrix. The simple parity check matrix is shown in Öberg, Mats and Siegel, Paul, Parity Check codes For Partial Response Channels, I.E.E.E. Global Telecommunications Conference—Globalcom '99, pages 717–722, 1999, the contents of which are incorporated by reference herein.
The SPC matrix is defined by two parameters, N and M, denoting the coded block length and the number of check equations, respectively. An example of an SPC matrix is shown in equation 4.
                              SPC          ⁡                      (                          N              ,              M                        )                          =                                            [                                                                                          11                      ⁢                                                                                          ⁢                      …                      ⁢                                                                                          ⁢                      100                      ⁢                                                                                          ⁢                      …                      ⁢                                                                                          ⁢                      0                                                                                                                                  00                      ⁢                                                                                          ⁢                      …                      ⁢                                                                                          ⁢                      011                      ⁢                                                                                          ⁢                      …                      ⁢                                                                                          ⁢                      100                      ⁢                                                                                          ⁢                      …                      ⁢                                                                                          ⁢                      0                                                                                                            …                                                                                        …                                                                                                              0                      ⁢                                                                                          ⁢                      …                      ⁢                                                                                          ⁢                      11                      ⁢                                                                                          ⁢                      …                      ⁢                                                                                          ⁢                      1                                                                                  ]                        N                    ⁢                      M            .                                              (        4        )            
The factor graph corresponding to this parity check matrix does not contain any cycles. This matrix also has a column weight tc=1. Column weight tc refers to the number of “1”s in each column. Since the complexity of the sum-product decoding algorithm increases linearly with tc, it is desirable to have a small tc. The minimum Hamming distance Dmin=2 for the SPC matrix of equation (4). The Hamming distance is the minimum number of columns that are linearly dependent in the parity check matrix. A large Dmin insures large separation between codewords, which results in a low bit error rate (BER). However, the coding gain of the SPC matrix of equation (4) is limited since Dmin=2. The code rate for the SPC matrix is 1−M/N.
Another conventional example of a parity check matrix is the interleaved parity check matrix in which additional parity check equations are added to the SPC matrix in an interleaved way to increase the Dmin. As shown in equation 5, an IPC matrix consists of two parts, the top part which is similar to an SPC matrix and the bottom part in which each row has the same number of “1”s. The IPC matrix can be specified by one parameter P, which is the number of “1”s in each row. This matrix has a dimension of 2P×P2. The coded block length is P2 and the number of parity check equations are 2P.
                              IPC          ⁡                      (            3            )                          =                  [                                                    111000000                                                                    000111000                                                                    000000111                                                                                      --                                      --                                          --                      -                                                                                                                          100100100                                                                    010010010                                                                    001001001                                              ]                                    (        5        )            
The IPC matrix does not contain any period-4 cycles, has a Dmin=4 and tc=2. As is understood by one of ordinary skill in the art, there are only 2P−1 independent rows in the parity check matrix. The code rate for the IPC matrix is (P2−2P+1)/P2.
One construction of a Dmin=6 parity check matrix is shown in equation 6. Its basis is an IPC matrix having P as an even number. It has a dimension of (3P−1)×P(P−1).
                              (          4          )                =                              [                                                            111100000000                                                                              000011110000                                                                              000000001111                                                                              100010001000                                                                              010001000100                                                                              001000100010                                                                              000100010001                                                                                                  --                                          --                                              --                                                  --                          -                                                                                                                                                                  100001000010                                                                              010000100001                                                                              001000010000                                                                              000100001000                                                      ]                    ⁢          IPC                                    (        6        )            
The upper part contains 2P−1 rows and the bottom part contains P rows where the “1”s are arranged diagonally with a shift of one column between each block. To obtain a Hamming distance of 6, then P−1, P and P+1 are relatively prime to each other. This matrix has a Dmin=6, there is no period-four cycle, tc=3−(1/(P+1)) or =3, and a code rate of (P2−4P+2)/(P2−P).